#define _Ty int
struct treap
{
    _Ty x;
    int y;
    treap *left, *right;
    treap (_Ty _x)
    {
        x = _x, y = rand() | 1 << rand(), left = right = NULL; 
    }
};

typedef *treap ptreap;
ptreap root = NULL;

void split(_Ty x, ptreap cur, ptreap &left, ptreap &right)
{
    if (!cur)
        left = right = NULL;
    else if (cur.x >= x)
        split(x, cur->left, left, cur->left), left = cur;
    else
        split(x, cur->right, cur->right, right), right = cur; 
}

ptreap merge(ptreap left, ptreap right)
{
    if (!left || !right)
        return (!right) ? left : right;
    if (left.y < right.y)
    {
        left->right = merge(left->right, right);
        return left;   
    }
    else
    {
        right->left = merge(left, right->left);
        return right;   
    }
}

void insert(_Ty x)
{
    ptreap left, right, place;
    split(x, root, left, right);
    split(x + 1, root, place, right);
    if (!place)
        place = new treap(x);
    right = merge(place, right);
    root = merge(left, right);
}

_Ty next(_Ty i)
	// returns minimal element, not greater then (i);
	// if such element does not exist, returns -1.
{
	ptreap left, right;
	_Ty result = 0;
	
	split(i, root, left, right);

	if (right != NULL)
	{
		ptreap temp = right;
		while (temp->left != NULL)
			temp = temp->left;
		result = temp->key;
	}
	else
		result = -1;

	root = merge(left, right);
	return result;
}
